package leetcode.tree_problem;

import java.util.ArrayList;
import java.util.Deque;
import java.util.LinkedList;
import java.util.List;

public class MyBinTree {

    public static class TreeNode{
        char val;
        int valInt;
        MyBinTree.TreeNode left;
        MyBinTree.TreeNode right;
        public TreeNode(char val) {
            this.val = val;
        }
    }

    public static TreeNode build(){
        TreeNode treeNodeA = new TreeNode('A');
        TreeNode treeNodeB = new TreeNode('B');
        TreeNode treeNodeC = new TreeNode('C');
        TreeNode treeNodeD = new TreeNode('D');
        TreeNode treeNodeE = new TreeNode('E');
        TreeNode treeNodeF = new TreeNode('F');
        TreeNode treeNodeG = new TreeNode('G');
        TreeNode treeNodeH = new TreeNode('H');
        treeNodeA.left = treeNodeB;
        treeNodeA.right = treeNodeC;
        treeNodeB.left = treeNodeD;
        treeNodeB.right = treeNodeE;
        treeNodeE.right = treeNodeH;
        treeNodeC.left = treeNodeF;
        treeNodeC.right = treeNodeG;
        return treeNodeA;
    }

    public static void preOrder(TreeNode root){//前序
        //不用返回值
        if (root == null)
            return ;
        System.out.println(root.val);
        preOrder(root.left);
        preOrder(root.right);
    }

    public static void inOrder(TreeNode root){//中序
        if (root == null){
            return;
        }
        inOrder(root.left);
        System.out.println(root.val);
        inOrder(root.right);

    }

    public static void postOrder(TreeNode root){
        if (root == null){
            return;
        }
        inOrder(root.left);
        inOrder(root.right);
        System.out.println(root.val);
    }

    public static int getNodes(TreeNode root){
        if (root == null){
            return 0;
        }
        return 1 + getNodes(root.left) + getNodes(root.right);
    }

    public static int getNodesLevelOrder(TreeNode root){
        if (root == null){
            return 0;
        }
        int size = 0;
        Deque<TreeNode> deque = new LinkedList<>();
        deque.offer(root);
        while (!deque.isEmpty()){
            TreeNode cur = deque.poll();
            size++;
            if (cur.left != null){
                deque.offer(cur.left);
            }
            if (cur.right != null){
                deque.offer(cur.right);
            }
        }
        return  size;
    }

    public static int getLeafNodes(TreeNode root){
        if (root == null){
            return 0;
        }
        if (root.left == null && root.right == null){
            return 1;
        }
        return getLeafNodes(root.left) + getLeafNodes(root.right);
    }

    public static int getLeafNodesLevelOrder(TreeNode root){
        if (root == null){
            return 0;
        }
        int size = 0;
        Deque<TreeNode> deque = new LinkedList<>();
        deque.offer(root);
        while (!deque.isEmpty()){
            TreeNode cur = deque.poll();
            if (cur.left == null && cur.right == null){
                size ++ ;
                //这里的continue嗯。。。不好说感觉没啥用
                continue;
            }
            if (cur.left != null){
                deque.offer(cur.left);
            }
            if (cur.right != null){
                deque.offer(cur.right);
            }
        }
        return size;

    }

    public static boolean contains(TreeNode root , int val){
        if (root == null){
            return false;
        }
        if (root.val == val){
            return true;
        }
        return contains(root.left , val) || contains(root.right , val);
    }

    public static int height(TreeNode root){
        if (root == null){
            return 0;
        }
        return 1 + Math.max(height(root.left) , height(root.right));
    }

    public static int getKLeveNodes(TreeNode root , int k){//以root为根的第层节点个数
        if (root == null || k <= 0){
            return 0;
        }
        if (k == 1){
            return 1;
        }
        return getKLeveNodes(root.left , k - 1) + getKLeveNodes(root.right , k -1);
    }
    public List<List<Integer>> levelOrder(TreeNode root) {
        List<List<Integer>> list = new ArrayList<>();
        if (root == null){
            return list;
        }
        Deque<TreeNode> deque = new LinkedList<>();
        deque.offer(root);
        while (!deque.isEmpty()){
            List<Integer> curList = new ArrayList<>();
            int size = deque.size();
            for (int i = 0; i < size; i++) {
                TreeNode cur = deque.poll();
                curList.add(cur.valInt);
                if (cur.left != null){
                    deque.offer(cur.left);
                }
                if (cur.right != null){
                    deque.offer(cur.right);
                }
            }
            list.add(curList);
        }
        return list;

    }
}
